package backtracking;

import java.util.Arrays;
import java.util.ArrayList;

public class SumasParciales2 {

	public static ArrayList<ArrayList<Integer>> combinationSum(
			int[] candidates, int target) {
		ArrayList<ArrayList<Integer>> sol = new ArrayList<ArrayList<Integer>>();
		Arrays.sort(candidates);
		combSumRec(candidates, target, new ArrayList<Integer>(), sol);
		return sol;
	}

	private static void combSumRec(int[] candidates, int target,
			ArrayList<Integer> partial, ArrayList<ArrayList<Integer>> sol) {
		int sum = 0;
		for (int i : partial)
			sum += i;
		if (sum == target) {
			if (!sol.contains(partial))
				sol.add(partial);
			return;
		} else if (sum > target)
			return;
		else {
			for (int i = 0; i < candidates.length; ++i) {
				ArrayList<Integer> partial_sol = new ArrayList<Integer>();
				partial_sol.addAll(partial);
				partial_sol.add(candidates[i]);
				int[] remaining = new int[candidates.length - i];
				System.arraycopy(candidates, i, remaining, 0, remaining.length);
				combSumRec(remaining, target, partial_sol, sol);
			}
		}
	}
	
	public static void main(String[] args){
		int[] c= {1,2,3,4,5,6};
		
		combinationSum(c,6);
	}

}